<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 字符串比较（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定字符串A、B和正整数V&#xff0c;A的长度与B的长度相等&#xff0c; 请计算A中满足如下条件的最大连续子串的长度&#xff1a;</p> 
<ol><li>该连续子串在A和B中的位置和长度均相同。</li><li>该连续子串|A[i] – B[i]|之和小于等于V。其中|A[i] – B[i]|表示两个字母<strong>ASCII码之差的绝对值</strong>。</li></ol> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入为三行&#xff1a;</p> 
<ul><li>第一行为字符串A&#xff0c;仅包含小写字符&#xff0c;1 &lt;&#61; A.length &lt;&#61;1000。</li><li>第二行为字符串B&#xff0c;仅包含小写字符&#xff0c;1 &lt;&#61; B.length &lt;&#61;1000。</li><li>第三行为正整数V&#xff0c;0&lt;&#61; V &lt;&#61; 10000。</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>字符串最大连续子串的长度&#xff0c;要求该子串|A[i] – B[i]|之和小于等于V。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"> <p>xxcdefg<br /> cdefghi<br /> 5</p> </td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p>字符串A为xxcdefg&#xff0c;字符串B为cdefghi&#xff0c;V&#61;5。</p> <p>它的最大连续子串可以是cd-&gt;ef,de-&gt;fg,ef-&gt;gh,fg-&gt;hi&#xff0c;所以最大连续子串是2。</p> </td></tr></tbody></table> 
<p></p> 
<h4>在线OJ</h4> 
<p><a href="https://hydro.ac/d/HWOD2023/p/OD168" rel="nofollow" title="题目详情 - 字符串比较 - HydroOJ">题目详情 - 字符串比较 - HydroOJ</a></p> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题其实可以转化为求解&#xff1a;和不超过v的最长连续子序列问题。</p> 
<p><img alt="" height="186" src="https://img-blog.csdnimg.cn/634f0e1948ce48e99268c5afe6a8053a.png" width="625" /></p> 
<p>原始数组就是上面的ascii码差值绝对值数组diff&#xff1a;[21, 20, 2, 2, 2, 2, 2] </p> 
<p></p> 
<p>本题数量级不大&#xff0c;diff数组的长度最大1000&#xff0c;因此我们只要求出区间和&lt;&#61;v的所有区间&#xff0c;取其中最长的即可。这里任意区间的区间和求解可以通过前缀和完成&#xff0c;具体可以看下面博客&#xff1a;</p> 
<p><a href="https://fcqian.blog.csdn.net/article/details/128976936" rel="nofollow" title="算法设计 - 前缀和 &amp; 差分数列_伏城之外的博客-CSDN博客">算法设计 - 前缀和 &amp; 差分数列_伏城之外的博客-CSDN博客</a></p> 
<hr /> 
<p>或者我们可以利用滑动窗口来求解&#xff1a;和不超过v的最长连续子序列问题。</p> 
<p>我们可以定义两个指针L,R&#xff0c;分别代表滑窗的左右边界&#xff0c;初始化时&#xff0c;L&#xff0c;R都为0&#xff0c;</p> 
<p>然后再定义一个滑窗内部和sum&#xff0c;初始为diff[r]</p> 
<p>接下来&#xff0c;判断sum和v的大小&#xff1a;</p> 
<ul><li>如果 sum &lt; v&#xff0c;则说明滑窗内部和过小&#xff0c;我们应该将滑窗的右边界R&#43;&#43;&#xff0c;来扩大滑窗&#xff0c;滑窗内部和sum &#43;&#61; diff[R]&#xff0c;需要注意的是&#xff0c;这里我们需要注意R越界问题&#xff0c;需要先判断R&#43;&#43;是否越界&#xff0c;如果未越界&#xff0c;才能sum &#43;&#61; diff[R]</li><li>如果 sum &#61;&#61; v&#xff0c;则说明滑窗内部和刚刚好&#xff0c;我们应该记录此时滑窗对应的连续子序列长度&#xff1a;R - L &#43; 1 作为一个可能解&#xff0c;接下来就是滑窗左右边界的移动问题&#xff1a;</li></ul> 
<blockquote> 
 <ol><li>按照以往滑窗运动经验&#xff0c;此时应该L&#43;&#43;&#xff0c;R&#43;&#43;&#xff0c;但是这里我们只应该做R&#43;&#43;&#xff0c;而不应该做L&#43;&#43;&#xff0c;原因是后续的diff[i]可能都是0&#xff0c;即不会增加sum&#xff0c;只会增加连续子序列的长度&#xff0c;因此如果这种情况做了L&#43;&#43;的话&#xff0c;我们会得不到最优解。</li><li>同样地&#xff0c;这里做R&#43;&#43;&#xff0c;也需要注意R越界问题&#xff0c;只有R&#43;&#43;后不越界&#xff0c;我们才能sum &#43;&#61; diff[R]</li></ol> 
</blockquote> 
<ul><li>如果 sum &gt; v&#xff0c;我们应该让滑窗左边界L&#43;&#43;&#xff0c;来减少sum&#xff0c;即sum -&#61; diff[L]&#xff0c;但是在做滑窗左边界L&#43;&#43;之前&#xff0c;我们应该确认一下&#xff0c;上一个状态的滑窗&#xff0c;即范围是[L, R-1]的滑窗是否是满足sum &lt;&#61; v的滑窗&#xff0c;如果是&#xff0c;则我们需要记录上一个滑窗的长度R - L</li></ul> 
<blockquote> 
 <ol><li>需要注意的是&#xff0c;当前滑窗做滑窗左边界L&#43;&#43;后&#xff0c;L是有可能超过R的&#xff0c;因此我们需要保证L超过R后&#xff0c;R的位置要更新到等于L的地方&#xff0c;此时又相当于给滑窗sum &#43;&#61; diff[R]</li><li>同样地&#xff0c;需要注意R更新位置的越界问题&#xff0c;即只有R&#61;L后不越界&#xff0c;才能sum &#43;&#61; diff[R]</li></ol> 
</blockquote> 
<p></p> 
<h3>前缀和解法</h3> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String a &#61; sc.nextLine();
    String b &#61; sc.nextLine();
    int v &#61; Integer.parseInt(sc.nextLine());

    System.out.println(getResult(a, b, v));
  }

  public static int getResult(String a, String b, int v) {
    int n &#61; a.length();

    // a,b字符串的各位字符的ascii绝对值差距数组
    int[] preSum &#61; new int[n &#43; 1];
    for (int i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
      preSum[i] &#61; preSum[i - 1] &#43; Math.abs(a.charAt(i - 1) - b.charAt(i - 1));
    }

    // 记录题解
    int ans &#61; 0;

    for (int l &#61; 0; l &lt;&#61; n - 1; l&#43;&#43;) {
      for (int r &#61; l &#43; 1; r &lt;&#61; n; r&#43;&#43;) {
        // 区间 [l&#43;1, r]的和 &#61; preSum[r] - preSum[l]
        if (preSum[r] - preSum[l] &lt;&#61; v) {
          ans &#61; Math.max(ans, r - l);
        }
      }
    }

    return ans;
  }
}
</code></pre> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 3) {
    let a &#61; lines[0];
    let b &#61; lines[1];
    let v &#61; parseInt(lines[2]);

    console.log(getResult(a, b, v));

    lines.length &#61; 0;
  }
});

function getResult(a, b, v) {
  const n &#61; a.length;

  // a,b字符串的各位字符的ascii绝对值差距数组
  const preSum &#61; new Array(n &#43; 1).fill(0);
  for (let i &#61; 1; i &lt;&#61; n; i&#43;&#43;) {
    preSum[i] &#61;
      preSum[i - 1] &#43; Math.abs(a[i - 1].charCodeAt() - b[i - 1].charCodeAt());
  }

  // 记录题解
  let ans &#61; 0;

  for (let l &#61; 0; l &lt;&#61; n - 1; l&#43;&#43;) {
    for (let r &#61; l &#43; 1; r &lt;&#61; n; r&#43;&#43;) {
      // 区间 [l&#43;1, r]的和 &#61; preSum[r] - preSum[l]
      if (preSum[r] - preSum[l] &lt;&#61; v) {
        ans &#61; Math.max(ans, r - l);
      }
    }
  }

  return ans;
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
a &#61; input()
b &#61; input()
v &#61; int(input())


# 算法入口
def getResult():
    n &#61; len(a)

    # a,b字符串的各位字符的ascii绝对值差距数组
    preSum &#61; [0] * (n&#43;1)
    for i in range(1, n&#43;1):
        preSum[i] &#61; preSum[i-1] &#43; abs(ord(a[i-1]) - ord(b[i-1]))

    # 记录题解
    ans &#61; 0

    for l in range(n):
        for r in range(l&#43;1, n&#43;1):
            # 区间 [l&#43;1, r]的和 &#61; preSum[r] - preSum[l]
            if preSum[r] - preSum[l] &lt;&#61; v:
                ans &#61; max(ans, r-l)

    return ans


# 调用算法
print(getResult())
</code></pre> 
<p></p> 
<h3>滑动窗口解法</h3> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String a &#61; sc.nextLine();
    String b &#61; sc.nextLine();
    int v &#61; Integer.parseInt(sc.nextLine());

    System.out.println(getResult(a, b, v));
  }

  public static int getResult(String a, String b, int v) {
    int n &#61; a.length();

    // a,b字符串的各位字符的ascii绝对值差距数组
    int[] diff &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      diff[i] &#61; Math.abs(a.charAt(i) - b.charAt(i));
    }

    // 记录题解
    int ans &#61; 0;

    // 滑窗左右边界
    int l &#61; 0;
    int r &#61; 0;

    // 初始滑窗的内部和
    int sum &#61; diff[r];

    while (r &lt; n) {
      if (sum &gt; v) {
        // 如果滑窗内部和超过了v&#xff0c;则我们需要先记录上一个滑窗[l, r-1]的长度
        if (sum - diff[r] &lt;&#61; v) ans &#61; Math.max(ans, r - l);
        // 然后由于当前滑窗内部和已经超过了v&#xff0c;因此需要减少滑窗内部和&#xff0c;只能让滑窗左边界&#43;1&#xff0c;内部和减去失去的diff[l]
        sum -&#61; diff[l&#43;&#43;];
        if (r &lt; l) {
          // 注意左边界右移不能超过右边界&#xff0c;如果超过了&#xff0c;则右边界也需要&#43;1&#xff0c;即变为左边界位置&#xff0c;此时内部和需要加入新右边界值diff[r]
          r &#61; l;
          if (r &lt; n) sum &#43;&#61; diff[r];
        }
      } else {
        // 如果滑窗内部和没有超过v
        if (sum &#61;&#61; v) {
          // 如果滑窗内部和&#61;&#61;v,那么当前滑窗就是一个符合要求的&#xff0c;需要记录此时滑窗[l,r]的长度
          ans &#61; Math.max(ans, r - l &#43; 1);
        }
        // 接下来只做滑窗右边界&#43;1&#xff0c;注意右边界不能越界&#xff0c;滑窗需要纳入新右边界只
        // 这里没有做左边界&#43;1 动作&#xff0c;是因为后续的diff有可能都为0&#xff0c;
        // 比如diff &#61; [0, 5, 0, 0, 0], v&#61;5, 当L&#61;0&#xff0c;R&#61;1时&#xff0c;符合当前条件&#xff0c;如果此处做了l&#43;&#43;,r&#43;&#43;,那么将得不到最大长度
        if (&#43;&#43;r &lt; n) sum &#43;&#61; diff[r];
      }
    }

    // 注意收尾处理&#xff0c;即最后必然是r越界&#xff0c;结束循环&#xff0c;因此最后一轮滑窗范围是[l, r-1]
    return Math.max(ans, r - l);
  }
}
</code></pre> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 3) {
    let a &#61; lines[0];
    let b &#61; lines[1];
    let v &#61; parseInt(lines[2]);

    console.log(getResult(a, b, v));

    lines.length &#61; 0;
  }
});

function getResult(a, b, v) {
  const n &#61; a.length;

  // a,b字符串的各位字符的ascii绝对值差距数组
  const diff &#61; new Array(n);
  for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
    diff[i] &#61; Math.abs(a[i].charCodeAt() - b[i].charCodeAt());
  }

  // 记录题解
  let ans &#61; 0;

  // 滑窗左右边界
  let l &#61; 0;
  let r &#61; 0;

  // 初始滑窗的内部和
  let sum &#61; diff[r];

  while (r &lt; n) {
    if (sum &gt; v) {
      // 如果滑窗内部和超过了v&#xff0c;则我们需要先记录上一个滑窗[l, r-1]的长度
      if (sum - diff[r] &lt;&#61; v) ans &#61; Math.max(ans, r - l);
      // 然后由于当前滑窗内部和已经超过了v&#xff0c;因此需要减少滑窗内部和&#xff0c;只能让滑窗左边界&#43;1&#xff0c;内部和减去失去的diff[l]
      sum -&#61; diff[l&#43;&#43;];
      if (r &lt; l) {
        // 注意左边界右移不能超过右边界&#xff0c;如果超过了&#xff0c;则右边界也需要&#43;1&#xff0c;即变为左边界位置&#xff0c;此时内部和需要加入新右边界值diff[r]
        r &#61; l;
        if (r &lt; n) sum &#43;&#61; diff[r];
      }
    } else {
      // 如果滑窗内部和没有超过v
      if (sum &#61;&#61; v) {
        // 如果滑窗内部和&#61;&#61;v,那么当前滑窗就是一个符合要求的&#xff0c;需要记录此时滑窗[l,r]的长度
        ans &#61; Math.max(ans, r - l &#43; 1);
      }
      // 接下来只做滑窗右边界&#43;1&#xff0c;注意右边界不能越界&#xff0c;滑窗需要纳入新右边界只
      // 这里没有做左边界&#43;1 动作&#xff0c;是因为后续的diff有可能都为0&#xff0c;
      // 比如diff &#61; [0, 5, 0, 0, 0], v&#61;5, 当L&#61;0&#xff0c;R&#61;1时&#xff0c;符合当前条件&#xff0c;如果此处做了l&#43;&#43;,r&#43;&#43;,那么将得不到最大长度
      if (&#43;&#43;r &lt; n) sum &#43;&#61; diff[r];
    }
  }

  // 注意收尾处理&#xff0c;即最后必然是r越界&#xff0c;结束循环&#xff0c;因此最后一轮滑窗范围是[l, r-1]
  return Math.max(ans, r - l);
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
a &#61; input()
b &#61; input()
v &#61; int(input())


# 算法入口
def getResult():
    n &#61; len(a)

    # a,b字符串的各位字符的ascii绝对值差距数组
    diff &#61; [0] * n
    for i in range(n):
        diff[i] &#61; abs(ord(a[i]) - ord(b[i]))

    # 记录题解
    ans &#61; 0

    # 滑窗左右边界
    l &#61; 0
    r &#61; 0

    # 初始滑窗的内部和
    total &#61; diff[r]

    while r &lt; n:
        if total &gt; v:
            # 如果滑窗内部和超过了v&#xff0c;则我们需要先记录上一个滑窗[l, r-1]的长度
            if total - diff[r] &lt;&#61; v:
                ans &#61; max(ans, r - l)
            # 然后由于当前滑窗内部和已经超过了v&#xff0c;因此需要减少滑窗内部和&#xff0c;只能让滑窗左边界&#43;1&#xff0c;内部和减去失去的diff[l]
            total -&#61; diff[l]
            l &#43;&#61; 1
            if r &lt; l:
                # 注意左边界右移不能超过右边界&#xff0c;如果超过了&#xff0c;则右边界也需要&#43;1&#xff0c;即变为左边界位置&#xff0c;此时内部和需要加入新右边界值diff[r]
                r &#61; l
                if r &lt; n:
                    total &#43;&#61; diff[r]
        else:
            # 如果滑窗内部和没有超过v
            if total &#61;&#61; v:
                # 如果滑窗内部和&#61;&#61;v,那么当前滑窗就是一个符合要求的&#xff0c;需要记录此时滑窗[l,r]的长度
                ans &#61; max(ans, r - l &#43; 1)
            # 接下来只做滑窗右边界&#43;1&#xff0c;注意右边界不能越界&#xff0c;滑窗需要纳入新右边界值
            # 这里没有做左边界&#43;1 动作&#xff0c;是因为后续的diff有可能都为0&#xff0c;
            # 比如diff &#61; [0, 5, 0, 0, 0], v&#61;5, 当L&#61;0&#xff0c;R&#61;1时&#xff0c;符合当前条件&#xff0c;如果此处做了l&#43;&#43;,r&#43;&#43;,那么将得不到最大长度
            r &#43;&#61; 1
            if r &lt; n:
                total &#43;&#61; diff[r]

    # 注意收尾处理&#xff0c;即最后必然是r越界&#xff0c;结束循环&#xff0c;因此最后一轮滑窗范围是[l, r-1]
    return max(ans, r-l)


# 调用算法
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>